package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/21 20:47
 */
public class MinimumNumberOfOperationsToMoveAllBallsToEachBox {


    /**
     * 暴力解法
     * @param boxes
     * @return
     */
    public int[] minOperations(String boxes) {
        int len = boxes.length();
        int[][] dp = new int[len][len];
        int[] answers = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if (boxes.charAt(j) == '1') {
                    dp[i][j] = Math.abs(j-i);
                }
                if (boxes.charAt(i) == '1') {
                    dp[j][i] = Math.abs(j-i);
                }
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                answers[i] += dp[i][j];
            }
        }

        return answers;
    }


    /**
     * 暴力解法2
     * @param boxes
     * @return
     */
    public int[] minOperations2(String boxes) {
        int len = boxes.length();
        int[] answers = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i != j && boxes.charAt(j) == '1') {
                    answers[i] += Math.abs(j-i);
                }
            }
        }
        return answers;
    }

    /**
     * 双向动态规划
     * @param boxes
     * @return
     */
    public int[] minOperations3(String boxes) {
        int len = boxes.length();

        /**
         * left数组表示
         *  left[i]: 下标为i的所有左边元素为1的都移动到i下标下需要的代价
         *  right[i]: 下标为i的所有右边元素为1的都移动到i下标下需要的代价
         */
        int[] left = new int[len];
        int[] right = new int[len];
        int oneNum = 0;
        for (int i = 1; i < len; i++) {
            if (boxes.charAt(i-1) == '1') {
                left[i] = left[i-1] + oneNum + 1;
                oneNum++;
            } else {
                left[i] = left[i-1] + oneNum;
            }
//            System.out.println("left[" + i + "] = " + left[i]);
        }

        oneNum = 0;
        for (int i = len-2; i >= 0; i--) {
            if (boxes.charAt(i+1) == '1') {
                right[i] = right[i+1] + oneNum + 1;
                oneNum++;
            } else {
                right[i] = right[i+1] + oneNum;
            }
        }

        int[] answers = new int[len];
        for (int i = 0; i < len; i++) {
            answers[i] = left[i] + right[i];
        }

        return answers;
    }
}
